#include <iostream>
#include <assert.h>
using namespace std;

template<class T>
struct AVLTreeNode
{
    typedef AVLTreeNode<T> Node;
    T _data;
    Node* _parent;
    Node* _left;
    Node* _right;
    int _bf;

    AVLTreeNode(const T& data)
        :_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)
    { }
    AVLTreeNode()
        :_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)
    { }
};

struct CMP_Big
{
    template<class T>
    bool operator()(const T& a, const T& b)
    {
        return a > b;
    }
};

struct CMP_Small
{
    template<class T>
    bool operator()(const T& a, const T& b)
    {
        return a < b;
    }
};



template<class K>
class SetKey 
{
public:
    const K& operator()(const K& v)
    {
        return v;
    }
};

template<class K, class T, class CMP, class KeyOfT>
class AVLTree
{
public:
    typedef AVLTreeNode<T> Node;

    template<class Ptr, class Ref>
    struct AVLIterator
    {
    private:
        Node* _node;
        AVLTree* _pt;
    public:
        typedef AVLIterator Self;

        AVLIterator(Node* node, AVLTree* pt)
            :_node(node), _pt(pt)
        { }


        Ref operator*()
        {
            return _node->_data;
        }

        Ptr operator->()
        {
            return &_node->_data;
        }

        bool operator!=(const Self& it)
        {
            return _node != it._node;
        }

        bool operator==(const Self& it)
        {
            return _node == it._node;
        }

        Self& operator++()
        {
            if (_node == nullptr)
            {
                Self s = _pt->begin;
                _node = s._node;
                return *this;
            }
            if (_node->_right)
            {
                Node* cur = _node->_right;
                while (cur->_left)
                {
                    cur = cur->_left;
                }
                _node = cur;
            }
            else
            {
                Node* cur = _node;
                Node* parent = cur->_parent;
                while (cur)
                {
                    if (parent && parent->_left == cur)
                    {
                        cur = parent;
                        break;
                    }
                    else
                    {
                        cur = parent;
                        if (cur)
                            parent = cur->_parent;
                    }
                }
                _node = cur;
            }
            return *this;
        }

        Self& operator--()
        {
            if (_node == nullptr)
            {
                Node* cur = _pt->_root;
                while (cur->_right)
                {
                    cur = cur->_right;
                }
                return *this;
            }
            if (_node->_left)
            {
                Node* cur = _node->_left;
                while (cur && cur->_right)
                {
                    cur = cur->_right;
                }
                _node = cur;
            }
            else
            {
                Node* cur = _node;
                Node* parent = cur->_parent;
                while (cur)
                {
                    if (parent && parent->_right == cur)
                    {
                        cur = parent;
                        break;
                    }
                    else
                    {
                        cur = parent;
                        if(cur)
                            parent = cur->_parent;
                    }
                }
                _node = cur;
            }
            return *this;
        }
    };

    typedef AVLIterator<T*, T&> iterator;
    typedef AVLIterator<const T*, const T&> const_iterator;

    iterator begin()
    {
        Node* cur = _root;
        while (cur->_left)
            cur = cur->_left;
        return iterator(cur, this);
    }

    iterator end()
    {
        return iterator(nullptr, this);
    }

    const_iterator begin() const
    {
        Node* cur = _root;
        while (cur->_left)
            cur = cur->_left;
        return const_iterator(cur, this);
    }

    const_iterator end() const
    {
        return const_iterator(nullptr, this);
    }

    AVLTree(const AVLTree& t)
    {
        _root = Copy(t._root);
    }

    AVLTree()
        :_root(nullptr)
    { }

    ~AVLTree()
    {
        Destroy(_root);
    }

    size_t size()
    {
        return _size;
    }

    bool Find(const K& k)
    {
        Node* cur = _root;
        while (cur)
        {
            if (k > _kot(cur->_data))
            {
                cur = cur->_right;
            }
            else if (k < _kot(cur->_data))
            {
                cur = cur->_left;
            }
            else return 1;
        }
        return 0;
    }

    pair<iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _size++;
            _root = new Node(data);
            return make_pair((_root, this), 1);
        }
        Node* cur = _root, * parent = nullptr;
        while (cur)
        {
            if (_kot(cur->_data) > _kot(data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (_kot(cur->_data) < _kot(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else return 0;
        }
        cur = new Node(data);
        if (_kot(parent->_data) > _kot(data))
        {
            parent->_left = cur;
            parent->_bf--;
        }
        else
        {
            parent->_right = cur;
            parent->_bf++;
        }
        cur->_parent = parent;
        cur = parent;
        parent = nullptr;
        while (cur)
        {
            if (cur->_bf == 1 || cur->_bf == -1)
            {
                if (!parent) break;
                if (parent->_left == cur) parent->_bf--;
                else parent->_bf++;

                cur = parent;
                parent = cur->_parent;
            }
            else if (cur->_bf == 0) break;
            else if (cur->_bf == 2 || cur->_bf == -2)
            {
                if (cur->_bf == 2 && cur->_right->_bf == 1)
                {
                    RotateR(cur);
                }
                else if (cur->_bf == -2 && cur->_left->_bf == -1)
                {
                    RotateL(cur);
                }
                else if (cur->_bf == 2 && cur->_right->_bf == -1)
                {
                    RotateRL(cur);
                }
                else if (cur->_bf == -2 && cur->_left->_bf == 1)
                {
                    RotateLR(cur);
                }
                break;
                //else assert(0);
            }
            //else assert(0);
        }

        return 1;
    }

    bool Erase(const T& data)
    {
        if (!Find(_kot(data))) return 0;
		Node* cur = _root;
		Node* parent = nullptr;
		while(cur)
		{
			parent = cur;
			if(_kot(data) > _kot(cur->_data))
			{
				cur = cur->_right;
			}
			else if(_kot(data) < _kot(cur->_data))
			{
				cur = cur->_left;
			}
			else break;
		} 
		Node parent_del = nullptr;
		const int LEFT = -1, RIGHT = 1;
		int dir = 0;
		if(cur->_right == nullptr)
		{
			if(!parent) 
			{
				_node = cur->_left;
				dir = LEFT;
			}
			else
			{
				if(parent->_letf == cur) parent->_left = cur->_left, dir = LEFT;
				else parent->_right = cur->_left, dir = RIGHT;
			}
			if(cur->_left) cur->_parent = parent;
			parent_del = parent;
			delete cur;
		} 
		else
		{
			Node* tmp = cur->_right;
			Node* parent_tmp = cur;
			while(tmp->_left)
			{
				tmp=tmp->_left;
			}
			swap(tmp->_data, cur->_data);
			if(parent_tmp->_left == tmp) parent_tmp->_left = nullptr, dir = LEFT;
			else parent_tmp->_right = nullptr, dir = RIGHT;
			delete tmp;
			parent_del = parent_tmp;
		}
		_size--;
		if(!_node) return 1;
		cur = parent_del;
		cur->_bf += dir;
		while(cur)
		{
			if(cur->_bf == 1 || cur->_bf == -1)
				break;
			else if(cur->_bf == 0)
			{
				parent = cur->_parent;
				if(!parent) break;
				if(parent->_left == cur)
				{
					parent->_bf++;
				}
				else parent->_bf--;
				cur = parnet
			}
			else if(cur->_bf == 2 || cur->_bf == -2)
			{
				if (cur->_bf == 2 && cur->_right->_bf == 1)
                {
                    RotateR(cur);
                }
                else if (cur->_bf == -2 && cur->_left->_bf == -1)
                {
                    RotateL(cur);
                }
                else if (cur->_bf == 2 && cur->_right->_bf == -1)
                {
                    RotateRL(cur);
                }
                else if (cur->_bf == -2 && cur->_left->_bf == 1)
                {
                    RotateLR(cur);
                }
                break;
                //else assert(0);
			}
			//else assert(0);
		}
		return 1;
    }

private:
    void Destroy(Node* root)
    {
        if (!root) return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
        return;
    }

    void RotateLR(Node* cur)
    {
        Node* SubL = cur->_left;
        Node* SubLR = SubL->_right;

        int memory = SubLR->_bf;
        RotateR(SubL);
        RotateL(cur);

        cur->_bf = SubL->_bf = SubLR->_bf = 0;
        if (memory == 0) {}
        else if (memory == 1)
        {
            SubLR->_bf = -1;
            SubL->_bf = -1;
        }
        else
        {
            cur->_bf = 1;
            SubLR->_bf = 1;
        }
    }

    void RotateRL(Node* cur)
    {
        Node* SubR = cur->_right;
        Node* SubRL = SubR->_left;

        int memory = SubRL->_bf;
        RotateL(SubR);
        RotateR(cur);
        SubR->_bf = SubRL->_bf = cur->_bf = 0;
        if (memory == 0) {}
        else if (memory == 1)
        {
            cur->_bf = 1;
            SubRL->_bf = -1;
        }
        else
        {
            SubR->_bf = -1;
            SubRL->_bf = 1;
        }
    }

    void RotateL(Node* cur)
    {
        Node* parent = cur->_parent;
        Node* SubL = cur->_left;
        Node* SubLR = SubL->_right;

        cur->_left = SubLR;
        if (SubLR) SubLR->_parent = cur;

        cur->_parent = SubL;
        SubL->_right = cur;

        SubL->_parent = parent;
        if (parent != nullptr)
        {
            if (parent->_left == cur)
                parent->_left = SubL;
            else parent->_right = SubL;
        }
        cur->_bf = SubL->_bf = 0;
    }

    void RotateR(Node* cur)
    {
        Node* parent = cur->_parent;
        Node* SubR = cur->_right;
        Node* SubRL = SubR->_left;

        cur->_right = SubRL;
        if (SubRL) SubRL->_parent = cur;

        cur->_parent = SubR;
        SubR->_left = cur;

        SubR->_parent = parent;
        if (parent != nullptr)
        {
            if (parent->_left == cur)
                parent->_left = SubR;
            else parent->_right = SubR;
        }
        cur->_bf = SubR->_bf = 0;
    }

    Node* Copy(Node* t)
    {
        if (nullptr = t) return nullptr;

        Node* left = Copy(t->left);
        Node* right = Copy(t->_right);
        Node* root = new Node(t->_data);

        root->_left = left;
        if (left) left->_parent = root;

        root->_right = right;
        if (right) right->_parent = root;

        return root;
    }

    Node* _root;
    CMP _cmp;
    KeyOfT _kot;
    size_t _size;
};
